package tree;
import java.util.*;
public class Ex617 {
    class Solution1 {
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            return merge(root1, root2);
        }

        public TreeNode merge(TreeNode r1, TreeNode r2) {
            if (r1 == null && r2 == null) return null;
            if (r1 == null || r2 == null) return r1 == null ? r2 : r1;
            r1.val += r2.val;
            r1.left = merge(r1.left, r2.left);
            r1.right = merge(r1.right, r2.right);
            return r1;
        }
    }
    class SolutionX {
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            if (root1 == null || root2 == null) return root1 == null ? root2 : root1;
            Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();
            s1.push(root1);
            s2.push(root2);
            TreeNode cur1, cur2;
            while (!s1.isEmpty() && !s2.isEmpty()) {
                cur1 = s1.pop();
                cur2 = s2.pop();
                cur1.val += cur2.val;
                if (cur1.left != null && cur2.left != null) {
                    s1.push(cur1.left);
                    s2.push(cur2.left);
                } else if (cur1.left == null) {
                    cur1.left = cur2.left; //key： 条件1不成立，表名此时cur1或者cur2必然有一个为空：若cur1为空
                    //，因为解法以cur1为标准，此时将cur2的right直接赋值cur1.left,表名将cur2后面的部分直接挂上去，后面就不必加了
                    //若cur2为空，直接结束
                }
               if (cur1.right != null && cur2.right != null) {
                    s1.push(cur1.right);
                    s2.push(cur2.right);
                } else if (cur1.right == null) {
                    cur1.right = cur2.right;
                }
            }
            return null;
        }
    }

    class Solution {
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        //如果 t1和t2中，只要有一个是null，函数就直接返回
            if(t1==null || t2==null) {
                return t1==null? t2 : t1;
            }
            java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<TreeNode>();
            queue.add(t1);
            queue.add(t2);
            while(queue.size()>0) {
                TreeNode r1 = queue.remove();
                TreeNode r2 = queue.remove();
                r1.val += r2.val;
                //如果r1和r2的左子树都不为空，就放到队列中
                //如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
                if(r1.left!=null && r2.left!=null){
                    queue.add(r1.left);
                    queue.add(r2.left);
                }
                else if(r1.left==null) {
                    r1.left = r2.left;
                }
                //对于右子树也是一样的
                if(r1.right!=null && r2.right!=null) {
                    queue.add(r1.right);
                    queue.add(r2.right);
                }
                else if(r1.right==null) {
                    r1.right = r2.right;
                }
            }
            return t1;
        }
    }

}
